﻿//// 添加逗号
//// https://ac.nowcoder.com/acm/problem/15054
//
//#include <iostream>
//#include <cstring>
//#include <string>
//#include <algorithm>
//#include <vector>
//#include <cmath>
//#include <unordered_map>
//#include <unordered_set>
//#include <map>
//#include <set>
//#include <queue>
//#include <stack>
//#include <deque>
//#include <functional>
//#include <climits>
//
//#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//#define endl "\n"
//
//using namespace std;
//typedef long long ll;
//
//void solve1()
//{
//    string s;
//    cin >> s;
//
//    int sz = s.size();
//    if (sz <= 3)
//    {
//        cout << s << endl;
//        return;
//    }
//
//    int mol = sz % 3, num = 0;
//    if (mol)
//    {
//        s.insert(s.begin() + mol, ',');
//        num++;
//    }
//    for (int i = mol + 3; i < sz - 1/*最后一位也不能打逗号*/; i += 3)
//    {
//        s.insert(s.begin() + i + num, ',');
//        num++;
//    }
//
//    cout << s << endl;
//}
//
//void solve2()
//{
//    /*
//        法一：模拟，每次取数字的最低位放入string中，每取三位就添加一个逗号，最后再逆置输出
//        法二：
//        string s = 4 3 2 7 6 8 3 2 1
//        下标 + 位数 = 数字长度
//        下标        0 1 2 3 4 5 6 7 8
//        位数        9 8 7 6 5 4 3 2 1
//        要加逗号的地方   ↑     ↑     ↑
//        (n - i - 1) % 3 == 0 && i != n - 1
//        n - i: 数字的位数
//    */
//    string s;
//    cin >> s;
//
//    int sz = s.size();
//    if (sz <= 3)
//    {
//        cout << s << endl;
//        return;
//    }
//
//    string ans;
//    for (int i = 0; i < sz; i++)
//    {
//        ans += s[i];
//        if ((sz - i - 1) % 3 == 0 && i != sz - 1)
//            ans += ',';
//    }
//    cout << ans << endl;
//}
//
//int main()
//{
//    solve2();
//    return 0;
//}

//DP2 跳台阶
//// https://www.nowcoder.com/practice/bfb2a2b3cdbd4bd6bba0d4dca69aa3f0?tpId=230&tqId=39749&ru=/exam/oj
//// 1有1个、2个、……、n个
//// 想法：1、排列组合    2、列举出前面几个台阶的走法个数，推出规律 -----------> 动态规划
//
//int dp[41];
//
//int solve()
//{
//    int n;
//    cin >> n;
//
//        /*考虑边界情况！！！！！！！！！！！！！*/
//    if (n == 0 || n == 1 || n == 2)
//        return n;
//
//    dp[1] = 1;
//    dp[2] = 2;
//    for (int i = 3; i <= n; i++)
//        dp[i] = dp[i - 1] + dp[i - 2]; /*考虑边界情况！！！！！！！！！！！！！*/
//    return dp[n];
//}
//
//跳台阶
//// https://ac.nowcoder.com/acm/problem/15319
//// 注意审题！！！！！！！！！！！！！！！他可以跳n步
//
//int dp[31];
//
//int solve()
//{
//    int n;
//    cin >> n;
//
//    memset(dp, 0, n * 4);
//
//    /*考虑边界情况！！！！！！！！！！！！！*/
//    if (n == 0 || n == 1 || n == 2)
//        return n;
//
//    dp[0] = 1;
//    dp[1] = 1;
//    dp[2] = 2;
//    for (int i = 3; i <= n; i++)
//    {
//        dp[i] = 0;
//        for (int j = 0; j < i; j++)
//            dp[i] += dp[j]; // 加上前面所有的方法数
//    }
//    return dp[n];
//}


//// JZ61 扑克牌顺子
//// https://www.nowcoder.com/practice/762836f4d43d43ca9deb273b3de8e1f4?tpId=13&tqId=11198&ru=/exam/oj
//
//// 考虑情况：0 0 11 12 13
//
//class Solution {
//public:
//    bool IsContinuous1(vector<int>& numbers)
//    {
//        // 排序
//        sort(numbers.begin(), numbers.end());
//        int num = 0, sz = numbers.size();
//
//        // 找0的个数
//        while (num < sz && !numbers[num])
//        {
//            num++;
//        }
//        // 如果0 的个数 == 5，则返回true
//        if (num == sz)
//            return true;
//
//        int x = num + 1, prev = numbers[num];
//        while (x < sz)
//        {
//            // 如果是重复数据
//            if (numbers[x] == prev)
//                return false;
//
//            // 不是顺子
//            if (numbers[x] != prev + 1)
//            {
//                // 没有办法构成顺子
//                if (num == 0)
//                    return false;
//
//                // 0的牌数目 - 1
//                num--;
//                // 该牌构成顺子
//                prev = prev + 1;
//            }
//            else
//            {
//                prev = numbers[x];
//                x++;
//            }
//        }
//
//        return true;
//    }
//
//    bool IsContinuous(vector<int>& numbers)
//    {
//        /*满足顺子的条件：1、没有重复元素   2、max - min <= 4*/
//
//        // 排序
//        sort(numbers.begin(), numbers.end());
//        int sz = numbers.size();
//        for (int i = 0; i < sz; i++)
//        {
//            if (i && numbers[i] && numbers[i] == numbers[i - 1])// 1、
//                return false;
//            if (numbers[i] && numbers[sz - 1] - numbers[i] > 4)// 2、
//                return false;
//        }
//        return true;
//    }
//};